/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/search-in-rotated-sorted-array-ii
   @Language: C++
   @Datetime: 16-02-09 08:29
   */

class Solution {
	/** 
	 * param A : an integer ratated sorted array and duplicates are allowed
	 * param target :  an integer to be search
	 * return : a boolean
	 * See problem 63: search in rotated sorted array
	 */
public:
	bool search(vector<int> &A, int target) {
		// write your code here
		int begin=0, end=A.size(), mid;
		if (end<1) return false;
		while (begin<end) {
			mid=(end-begin)/2+begin;
			if (A[mid]==target) return true;
			if (A[mid]==A[begin]) ++begin;
			else if (A[begin]<=A[mid]){
				if (A[mid]>=target && A[begin]<=target) end=mid;
				else begin=mid+1;
			}
			else{
				if (A[mid]<=target && A[end-1]>=target) begin=mid+1;
				else end=mid;
			}
		}
		return A[mid]==target;
	}
};
